#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <ctime>



/*****定义*****/
struct Node
{
    int data;
    struct Node *next;
};
typedef struct Node Node;
typedef struct Node *LinkList;



/*****核心功能函数*****/
LinkList MergeListR(LinkList &La, LinkList &Lb)
{
    LinkList pa, pb, pc, p1, p2;
    pa = La->next;
    pb = Lb->next;
    pc = La;
    p1 = La->next;
    p2 = Lb->next;
    La->next = NULL;

    while (pa != NULL && pb != NULL)
    {
        if (pa->data < pb->data)
        {
            pc = pa->next;
            pa->next = La->next;
            La->next = pa; // 每次把小的数插入到La的下一个位置，类似头插法
            pa = pc;
        }
        else if (pa->data > pb->data)
        {
            pc = pb->next;
            pb->next = La->next;
            La->next = pb; // 每次把小的数插入到La的下一个位置，类似头插法
            pb = pc;
        }
        else
        {
            pc = pa->next;
            pa->next = La->next;
            La->next = pa; // 每次把小的数插入到La的下一个位置，类似头插法
            pa = pc;
            pb = pb->next;
        }
    }
    while (pa != NULL) // 已经提前去掉了重复的数据
    {
        pc = pa->next;
        pa->next = La->next;
        La->next = pa;
        pa = pc;
    }
    while (pb != NULL) // 已经提前去掉了重复的数据
    {
        pc = pb->next;
        pb->next = La->next;
        La->next = pb;
        pb = pc;
    }

    if (p1->data <= p2->data)
    {
        p1->next = NULL;
    }
    else
    {
        p2->next = NULL;
    }
    return La;
}



/*****随机生成一个长度为l的单链表（未排序并且有头结点）*****/
LinkList List_TailInsert(int l, LinkList &L)
{
    int k = 1;
    int x = 0;
    L = (LinkList)malloc(sizeof(Node)); // 创建头结点
    LinkList s;
    LinkList r = L; // r为表尾指针
    while (k <= l)
    {
        x = rand() % 101;
        s = (LinkList)malloc(sizeof(Node)); // 由系统生成一个Node型的结点，同时将该结点的起始位置赋值给指针变量s
        s->data = x;
        r->next = s;
        r = s;
        k = k + 1;
        printf("%d ", x);
    }
    r->next = NULL;
    printf("\n");
    return L;
}



/*****冒泡排序*****/
LinkList BubbleSort(LinkList &L) //对单链表进行冒泡排序
{
    LinkList pa, pb, pc;
    int c = 0;
    pa = L->next;
    pb = L->next->next;
    pc = L->next;
    
    //求链表长度
    int l = 0;
    while (pc != NULL)
    {
        l = l + 1;
        pc = pc->next;
    }
    
    int j = 1;
    while (j < l)
    {
        if (pa->data > pb->data)
        {
            c = pb->data;
            pb->data = pa->data;
            pa->data = c;
            j = 1;
        }
        else
        {
            j = j + 1;
        }
        pb = pb->next;
        pa = pa->next;
        if (pa->next == NULL && j != l)
        {
            j = 1;
            pa = L->next;
            pb = L->next->next;
        }
    }
    pc = L->next;
    while (pc != NULL)
    {
        printf("%d ", pc->data);
        pc = pc->next;
    }
    printf("\n");
    return L;
}



/*****排序后单链表删重函数*****/
LinkList opt(LinkList &L)
{
    LinkList p0, p1;
    p0 = L->next;
    p1 = p0->next;
    while (p1 != NULL)
    {
        if (p0->data != p1->data)
        {
            p0 = p0->next;
            p1 = p1->next;
        }
        else
        {
            p1 = p1->next;
            p0->next = p1;
        }
    }
    return L;
}



/*****输出一个单链表*****/
void printd(LinkList L)
{
    LinkList p = L->next;
    while (p != NULL)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}



/*****主函数*****/
int main()
{
    //生成两个乱序的单链表，这里规定了第一个长度为12，第二个长度为8
    LinkList La = NULL;
    LinkList Lb = NULL;
    srand(time(0));
    printf("  生成的第一个单链表：");
    La = List_TailInsert(12, La);
    printf("  生成的第二个单链表：");
    Lb = List_TailInsert(8, Lb);

    //对两个链表进行排序
    printf("排序后的第一个单链表：");
    La = BubbleSort(La);
    printf("排序后的第二个单链表：");
    Lb = BubbleSort(Lb);

    //对排序后的单链表进行优化（删除单链表中的重复数据）
    La = opt(La);
    Lb = opt(Lb);

    //执行功能函数
    La = MergeListR(La, Lb);

    //输出符合题意的单链表
    printf("按题意处理后的单链表：");
    printd(La);

    //防止运行后自动退出，需头文件【stdlib.h】
    system("pause"); 
}